package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了95.32%的用户
内存消耗：2.6 MB, 在所有 Go 提交中击败了99.95%的用户
 */
func longestPalindrome(s string) string {

	if len(s) < 2 {
		return s
	}

	start, length := 0, 1
	for i := 0; i < len(s); i++ {
		cur := max(get(s, i, i), get(s, i, i + 1))
		if cur > length {
			length = cur
			start = i - (length - 1) / 2
		}
	}
	return s[start : start + length]
}

func get(s string, i int, j int) int {

	for i >= 0 && j < len(s) {
		if s[i] != s[j] {
			break
		}
		i--
		j++
	}
	return j - i - 1
}

func max(a int, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func main() {

	fmt.Println(longestPalindrome("babad"))  // bab
}
